package com.zhanghp.class06;

import com.zhanghp.refer.TreeNode;

/**
 * <h1>判断是否是搜索二叉树</h1>
 * <p>给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。</p>
 * <ul>
 *     <font style="color:#FFF2E2">有效</font>二叉搜索树定义如下：
 *     <li>
 *          节点的左子树只包含<font style="color:#FFF2E2">小于</font>当前节点的数。
 *     </li>
 *     <li>
 *          节点的右子树只包含<font style="color:#FFF2E2">大于</font>当前节点的数。
 *     </li>
 *     <li>
 *          所有左子树和右子树自身必须也是二叉搜索树。
 *     </li>
 * </ul>
 * <a href = "https://leetcode.cn/problems/validate-binary-search-tree/description/">leetcode</a>
 *
 * @author zhp
 * @since 2024/1/23 11:03
 */
public class Code03_IsBinarySearchTree {
    public boolean isValidBST(TreeNode root) {
        return process(root).isBST;

    }

    public TreeInfo process(TreeNode x) {
        if (x == null) {
            return null;
        }
        TreeInfo leftInfo = process(x.left);
        TreeInfo rightInfo = process(x.right);
        int min;
        int max;
        boolean isBST;
        // 初始化，防止左右树有一个为空
        max = min = x.val;
        // 最大值，最小值设定
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        // 最大值，最小值设定
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }
        // 左树是否是BST
        boolean leftIsBST = leftInfo == null || leftInfo.isBST;
        // 右树是否是BST
        boolean rightIsBST = rightInfo == null || rightInfo.isBST;
        // 左树最大值 是否小于 根节点的值
        boolean leftMaxLessVal = leftInfo == null || x.val > leftInfo.max;
        // 右树最小值 是否小于 根节点的值
        boolean rightMinMoreVal = rightInfo == null || x.val < rightInfo.min;
        isBST = leftIsBST && rightIsBST && leftMaxLessVal && rightMinMoreVal;
        return new TreeInfo(isBST, max, min);
    }

    public static class TreeInfo {

        /**
         * 当前树是否是搜索树
         */
        public boolean isBST;

        /**
         * 当前树的最大节点值
         */
        public int max;

        /**
         * 当前树的最小节点值
         */
        public int min;

        public TreeInfo(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

}
